First unique character in a string

Time: O(N); Space: O(N); easy

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Example 1:

Input: s = “leetcode”

Output: 0

Example 2:

Input: s = “loveleetcode”

Output: 2

Note:

  • You may assume the string contain only lowercase letters.

1. Linear time solution [O(N), O(N)]

The best possible solution here could be of a linear time because to ensure that the character is unique you have to check the whole string anyway.

The idea is to go through the string and save in a hash map the number of times each character appears in the string. That would take O(N) time, where N is a number of characters in the string.

And then we go through the string the second time, this time we use the hash map as a reference to check if a character is unique or not. If the character is unique, one could just return its index. The complexity of the second iteration is O(N) as well.

[6]:

import collections

class Solution1(object):
    """
    Time: O(N) since we go through the string of length N two times.
    Space: O(N) since we have to keep a hash map with N elements.
    """
    def firstUniqChar(self, s) -> int:
        """
        :type s: str
        :rtype: int
        """
        # build hash map : character and how often it appears
        count = collections.Counter(s)

        # find the index
        for idx, ch in enumerate(s):
            if count[ch] == 1:
                return idx
        return -1

[7]:

sol = Solution1()
s = "leetcode"
assert sol.firstUniqChar(s) == 0
s = "loveleetcode"
assert sol.firstUniqChar(s) == 2

2. Linear time solution [O(N), O(N)]

[8]:

from collections import defaultdict

class Solution2(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def firstUniqChar(self, s) -> int:
        """
        :type s: str
        :rtype: int
        """
        lookup = defaultdict(int)
        candidtates = set()

        for i, c in enumerate(s):
            if lookup[c]:
                candidtates.discard(lookup[c])
            else:
                lookup[c] = i+1
                candidtates.add(i+1)

        return min(candidtates)-1 if candidtates else -1

[9]:

sol = Solution2()
s = "leetcode"
assert sol.firstUniqChar(s) == 0
s = "loveleetcode"
assert sol.firstUniqChar(s) == 2